13.9 KB · ⇊ 9 parts · ⤓ Micron 13.9 KB · ⤓ HTML 41.7 KB

top

Superoptimization is the process where a compiler automatically finds the optimal sequence for a loop-free sequence of instructions. Real-world compilers generally cannot produce genuinely optimal code, and while most standard compiler optimizations only improve code partly, a superoptimizer's goal is to find the optimal sequence, the canonical form. Superoptimizers can be used to improve conventional optimizers by highlighting missed opportunities so a human can write additional rules.

• History

• Techniques

• Publicly available superoptimizers

• See also

• References

The term superoptimization was first coined by Alexia Massalin in the 1987 paper Superoptimizer: A Look at the Smallest Program.cite-ref-massalin-1987-superoptimizer-1-0[1] The label "program optimization" has been given to a field that does not aspire to optimize but only to improve. This misnomer forced Massalin to call her system a superoptimizer, which is actually an optimizer to find an optimal program.cite-ref-denali-2-0[2]

In 1992, the GNU Superoptimizer (GSO) was developed to integrate into the GNU Compiler Collection (GCC).cite-ref-gccsuperacm-3-0[3]cite-ref-gccsuperopt-4-0[4] Later work further developed and extended these ideas.

Traditionally, superoptimizing is performed via exhaustive brute-force search in the space of valid instruction sequences. This is a costly method, and largely impractical for general-purpose compilers. Yet, it has been shown to be useful in optimizing performance-critical inner loops. It is also possible to use a SMT solver to approach the problem, vastly improving the search efficiency (although inputs more complex than a basic block remains out of reach).cite-ref-jangda-5-0[5]

In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.cite-ref-joshi-2001-6-0[6] In 2006, answer set declarative programming was applied to superoptimization in the Total Optimisation using Answer Set Technology (TOAST) projectcite-ref-toast-krr-7-0[7] at the University of Bath.cite-ref-toast-book-8-0[8]cite-ref-crick-phd-9-0[9]

Superoptimization can be used to automatically generate general-purpose peephole optimizers.cite-ref-bansal-2006-10-0[10]

Several superoptimizers are available for free download.

• For the x86 family of instruction sets:

• GNU superoptimizer (superopt)cite-ref-gso-1992-11-0[11] (GSO) (1992)cite-ref-gccsuperacm-3-1[3]cite-ref-gccsuperopt-4-1[4] – also supports many other ISAs

• STOKE,cite-ref-stoke-12-0[12] a stochastic optimizercite-ref-bansal-2008-13-0[13] for x86-64 x86 assembly language.

• For ARM:

• Unbounded Superoptimizer,cite-ref-jangda-5-1[5] transforming LLVM IR into ARMv7-A assembly

• For embedded systems:

• PIC microcontroller SuperOptimizer (2003)cite-ref-serpell-2003-1-14-0[14]cite-ref-serpell-2003-2-15-0[15]

• A feasibility study by Embecosm (2014) for AVR, based on GSOcite-ref-embecosm-2014-16-0[16]cite-ref-17[17]

• For the JVM:

• Clojure superoptimizer for the Java virtual machine (2012)cite-ref-hume-2012-18-0[18]

• For LLVM IR:

• soupercite-ref-souper-19-0[19] superoptimizer for programs in the LLVM intermediate language.

• For WebAssembly

• slumpscite-ref-slumps-20-0[20] provides superoptimization for WASM programs based on souper.

• Peephole optimization

• Dead code elimination

• Metacompilation

cite-note-massalin-1987-superoptimizer-11. ↑ citerefmassalin1987Massalin, Henry (1987). "Superoptimizer: A look at the smallest program" (PDF). ACM SIGARCH Computer Architecture News. 15 (5): 122–126. doi:10.1145/36177.36194. Retrieved 2023-05-01. Given an instruction set, the superoptimizer finds the shortest program to compute a function. Startling programs have been generated, many of them engaging in convoluted bit-fiddling bearing little resemblance to the source programs which defined the functions. The key idea in the superoptimizer is a probabilistic test that makes exhaustive searches practical for programs of useful size.

cite-note-denali-22. ↑ citerefjoshinelsonrandall2002Joshi, Rajeev; Nelson, Greg; Randall, Keith (2002). "Denali: A Goal-directed Superoptimizer". ACM SIGPLAN Notices. 37 (5): 304–314. doi:10.1145/543552.512566.

cite-note-gccsuperacm-33. ↑ citerefgranlundkennerGranlund, Torbjörn; Kenner, Richard. "Eliminating branches using a superoptimizer and the GNU C compiler". Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation - PLDI '92. CiteSeerX 10.1.1.58.3509. doi:10.1145/143095.14314. ISBN 978-0-89791475-8. S2CID 8825539.

cite-note-gccsuperopt-44. ↑ "Index of /gnu/superopt". GNU Operating System. Free Software Foundation, Inc. 1995-06-14. Retrieved 2023-05-01.

cite-note-jangda-55. ↑ citerefjangdayorsh2017Jangda, Abhinav; Yorsh, Greta (2017-10-25). Unbounded superoptimization. Onward!’17, October 25–27, 2017, Vancouver, Canada. pp. 78–88. doi:10.1145/3133850.3133856.

cite-note-joshi-2001-66. ↑ citerefjoshinelsonrandall2001Joshi, Rajeev; Nelson, Greg; Randall, Keith (2001-07-30). "Denali: a goal-directed superoptimizer". Compaq Systems Research Center. HP Labs. Hewlett-Packard Co. Retrieved 2023-05-01.

cite-note-toast-krr-77. ↑ "TOAST – KRRwiki". Department of Computer Science, Mathematical Foundations Group. Knowledge Representation and Reasoning (KRR) group. University of Bath. 2007-08-07. Archived from the original on 2012-11-28. Retrieved 2016-09-03.

cite-note-toast-book-88. ↑ citerefbraincrickde-vosfitch2006Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (2006-08-17). "TOAST: Applying Answer Set Programming to Superoptimisation". In Etalle, Sandro; Truszczyński, Mirosław (eds.). Logic Programming. Springer-Verlag. pp. 270–284. doi:10.1007/11799573_21. ISBN 978-3-540-36636-2.

cite-note-crick-phd-99. ↑ citerefcrick2009Crick, Tom (2009). Superoptimisation: Provably Optimal Code Generation using Answer Set Programming (PhD thesis). University of Bath. Retrieved 2024-11-15.

cite-note-bansal-2006-1010. ↑ citerefbansalaiken2006Bansal, Sorav; Aiken, Alex (2006). "Automatic Generation of Peephole Superoptimizers" (PDF). Retrieved 2023-05-01.

cite-note-gso-1992-1111. ↑ "GNU Superoptimizer".

cite-note-stoke-1212. ↑ citerefstanfordplStanfordPL. "STOKE". GitHub.

cite-note-bansal-2008-1313. ↑ citerefbansalaiken2008Bansal, Sorav; Aiken, Alex (2008). "Binary Translation Using Peephole Superoptimizers" (PDF). Retrieved 2023-05-01.

cite-note-serpell-2003-1-1414. ↑ citerefserpell2003Serpell, Daniel (2003). "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites. Archived from the original on 2016-10-11. Retrieved 2016-09-06.

cite-note-serpell-2003-2-1515. ↑ citerefserpell2003Serpell, Daniel (2003-06-21). "PIC Microcontroller SuperOptimizer". Freecode. Slashdot Media. Archived from the original on 2016-09-17. Retrieved 2016-09-06.

cite-note-embecosm-2014-1616. ↑ "A feasibility study by Embecosm".

cite-note-1717. ↑ Superoptimization – Embecosm Source Code

cite-note-hume-2012-1818. ↑ citerefhume2012Hume, Tom (2012-08-21). "Clojure program to exhaustively search for optimal Java programs". GitHub. Archived from the original on 2018-06-10. Retrieved 2016-09-06.

cite-note-souper-1919. ↑ citerefsasnauskaschencollingbourneketema2017Sasnauskas, Raimondas; Chen, Yang; Collingbourne, Peter; Ketema, Jeroen; Lup, Gratian; Taneja, Jubi; Regehr, John (2017). "Souper: A Synthesizing Superoptimizer". arXiv:1711.04422 [cs.PL]. GitHub source code

cite-note-slumps-2020. ↑ citerefcabrera-arteagadondegufloros2020Cabrera Arteaga, Javier; Donde, Shrinish; Gu, Jian; Floros, Orestis; Satabin, Lucas; Baudry, Benoit; Monperrus, Martin (2020-03-23). Superoptimization of WebAssembly bytecode. MoreVMs: Workshop on Modern Language Runtimes, Ecosystems, and VMs. pp. 36–40. arXiv:2002.10213. doi:10.1145/3397537.3397567. GitHub source code